A balanced tree (b-tree) is a data structure often used to store data in a sorted order. B-trees are particularly applicable to database operations in which access to large amounts of data in a sorted order is typically required. Using a b-tree to store data allows data in the b-tree to be easily retrieved in sorted order. It is also possible to use the sorted order to access individual data items in the b-tree based on their ordinal position within the sorted order (e.g., the nth item in a sorted set of data). This type of access is known as positional access.
Positional access utilizing a b-tree conventionally includes computing or approximating the position of a data item in the b-tree. For example, if a b-tree stores 2n different values in its leaves, then using the assumption that a b-tree distributes data roughly evenly from left to right it can be estimated that the nth sorted item appears roughly halfway across the leaf level of the b-tree. However, the exact size of a b-tree, and the exact distribution of data across the b-tree, is not typically known when a search begins. That is, the exact number of values in leaf nodes of the b-tree, as well as how evenly distributed those values are, may not be known. Thus, if all that it known about a sought item is that it is the nth item in a sorted order, it can still be difficult to locate the item with precision. Moreover, it is difficult even to confirm how accurate the estimate is, since in general, determining whether a given data item is the nth data item involves traversing the tree down to its leaves to determine how many data items precede the given data item. Therefore, a technique for positional access utilizing a b-tree that does not suffer the above disadvantages is desired.